import collections


class Solution(object):
    def isValid(self, code):
        """
        :type code: str
        :rtype: bool
        """
        n = len(code)
        if code[0] != '<':
            return False
        left_index = 1
        right_index = 1
        stack = collections.deque()
        state = 0
        while right_index < n:
            if state == 0:
                if code[right_index] == '>':
                    if right_index - left_index == 0 or right_index - left_index > 9:
                        return False
                    else:
                        stack.append(code[left_index: right_index])
                        left_index = right_index + 1
                        state = 1
                else:
                    if ord(code[right_index]) < ord('A') or ord(code[right_index]) > ord('Z'):
                        return False
            else:
                if state == 1:
                    if code[right_index] == '<':
                        state = 2
                else:
                    if state == 2:
                        if code[right_index] == '/':
                            left_index = right_index + 1
                            state = 3
                        else:
                            if code[right_index] == '!':
                                if right_index + 7 < n and code[right_index: right_index + 8] == '![CDATA[':
                                    state = 4
                                    left_index = right_index + 8
                                    right_index = left_index - 1
                                else:
                                    return False
                            else:
                                if ord('A') <= ord(code[right_index]) <= ord('Z'):
                                    state = 0
                                    left_index = right_index
                                else:
                                    return False
                    else:
                        if state == 3:
                            if code[right_index] == '>':
                                if code[left_index: right_index] == stack[-1]:
                                    stack.pop()
                                else:
                                    return False
                                if stack:
                                    state = 1
                                else:
                                    state = -1
                                left_index = right_index + 1
                        else:
                            if state == 4:
                                if right_index + 2 < n:
                                    if code[right_index: right_index + 3] == ']]>':
                                        state = 1
                                        left_index = right_index + 3
                                        right_index = left_index - 1
                                else:
                                    return False
                            else:
                                break
            right_index += 1
        if state == -1 and right_index == n:
            return True
        else:
            return False


data = Solution()
code = "<DIV>T<![CDATA[<div>]]></DIV>"
print(data.isValid(code))
code = "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
print(data.isValid(code))
code = "<A></A><B></B>"
print(data.isValid(code))
code = "<A>  <B> </A>   </B>"
print(data.isValid(code))
code = "<DIV>  div tag is not closed  <DIV>"
print(data.isValid(code))
code = "<DIV>  unmatched <  </DIV>"
print(data.isValid(code))
code = "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
print(data.isValid(code))
code = "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
print(data.isValid(code))
code = "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
print(data.isValid(code))
code = "<A><![CDATA[<B></A>]]></B></A>"
print(data.isValid(code))
